/*
 * @lc app=leetcode.cn id=981 lang=typescript
 *
 * [981] 基于时间的键值存储
 */

// @lc code=start
class TimeMap {
  data: Map<string, [number, string][]>;
  constructor() {
    this.data = new Map();
  }

  set(key: string, value: string, timestamp: number): void {
    if (this.data.has(key)) {
      this.data.get(key).push([timestamp, value]);
    } else {
      this.data.set(key, [[timestamp, value]]);
    }
  }

  get(key: string, timestamp: number): string {
    if (!this.data.has(key)) {
      return '';
    }
    // 二分查找二元数组中第一个小于等于timestamp的value
    let time = this.data.get(key);
    let l = 0;
    let r = time.length - 1;
    let mid: number;
    while (l <= r) {
      mid = l + ((r - l) >> 1);
      if (time[mid][0] === timestamp) return time[mid][1];
      if (time[mid][0] <= timestamp) l = mid + 1;
      else r = mid - 1;
    }
    if (r >= 0) {
      return time[r][1];
    } else {
      return '';
    }
  }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */
// @lc code=end
